using BepuUtilities;
using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;
#if MYCODE
using BepuUtilities.Vectors;
#else
using System.Numerics;
#endif
namespace BepuPhysics.Trees
{
    partial struct Tree
    {
        // 待办事项：
        // 有一些继承自原型的问题,我们希望在某个时候解决：
        // 1)递归。这里没有理由使用递归。
        // 2)使用单线程变体重复工作。当前的负载平衡方法使用单线程路径深入到树中,并且该逻辑
        // 基本上是一模一样的。如果有一个将两者统一起来的零开销抽象,那就太好了。不清楚这有多大用处-有可能
        // 最终会比仅仅两个近乎相同的实现更加复杂。
        // 3)偷工量有限。虽然我们可以在第一个过程中任意俯冲很远,但它增加了单线程阶段。
        // 如果窄相位依赖于宽相位进行其工作平衡(即,重叠处理器直接触发窄相位工作),
        // 您可能需要深入研究以维护负载平衡,以至于单线程阶段开始有意义地限制并行性。
        // 不过,任何小于~5us的固定成本基本上都是无关紧要的-如果您可以收集128个节点对在5us内进行测试,这很可能足以对窄相位进行负载平衡
        // 即使在大约16个内核上也是如此。
        // 4)如果处理程序直接执行窄阶段工作,则在单线程收集阶段处理的重叠可能会很糟糕。对于任何不平凡的人来说,这应该是相当罕见的
        // 树,但在角落的情况下还是要注意的。

        // 要具体解决上面的第三点,请考虑显性的工作窃取。当工作者离开直接可访问的工作时(其耗尽了自己的堆栈,并且不再存在预先收集的根),
        // 它可以窥探其他工作堆栈。这将在每个堆栈上引入同步要求。
        // 1)盗窃者可能会从索赔0开始,然后向前走。最大的作业位于堆栈的顶部,这为您提供了最大的同步工作回报。
        // 它将检查每个堆栈条目的声明状态-每个条目上都会有一个整数将其标记为声明或未声明。一旦找到候选者,请比较Exchange以认领它。
        // 它必须区分"偷来的"区块和当地认领的区块。小偷可以跨过偷来的街区,但如果它击中了当地声称的挡路,它就必须停止。
        // 2)虽然将新作业推送到本地堆栈是免费的,但受害者必须始终检查以确认堆栈弹出不会消耗已被其他线程窃取的作业。
        // 考虑到浅层堆栈访问往往工作量较少,本地线程可能更喜欢一次声明其堆栈的大块。它可以简单地通过以下方式做到这一点
        // 在堆栈元素上执行所需数量的堆栈向上元素的比较交换。由于窃贼总是按部就班地工作,没有留下任何间隙,所以本地线程
        // 可以通过在堆栈中的任何(无人认领的)点声明来挡路它们。所有以后的堆栈条目都可以不受影响。实际上,这意味着本地线程应该能够
        // 避免对绝大多数POP操作执行联锁操作。

        // 有了这样的计划,你仍然想以某种方式收集一组最初的工作,给员工提供一些可以咀嚼的东西,但你不再需要每个员工有很多工作。
        // 因此,如果您有一台128核的计算机,您仍然可以拥有大约256个作业-即使在频率较低的处理器上,您也可能在不到20us的时间内收集到这些作业
        // (就像您在128核机器上可以找到的那样)。

        public class MultithreadedSelfTest<TOverlapHandler> where TOverlapHandler : struct, IOverlapHandler
        {
            struct Job
            {
                public int A;
                public int B;
            }

            public BufferPool Pool;

            int NextNodePair;
            int leafThreshold;
            private QuickList<Job> jobs;
            public int JobCount => jobs.Count;
            public Tree Tree;
            public TOverlapHandler[] OverlapHandlers;

            public MultithreadedSelfTest(BufferPool pool)
            {
                Pool = pool;
            }

            /// <summary>
            /// 准备与自检关联的作业。必须在通过PairTest进行调度之前调用。
            /// </summary>
            /// <param name="tree">要针对自身进行测试的树。</param>
            /// <param name="overlate Handler">用于处理自检检测到的单个重叠的回调。</param>
            /// <param name="threadcount">要准备作业的线程数。</param>
            public void PrepareJobs(ref Tree tree, TOverlapHandler[] overlapHandlers, int threadCount)
            {
                // 如果没有多个子级,则不需要递归。
                // 这保证了GetOverlapsInNode考虑的每个内部节点中至少有2个子节点。
                if (tree.leafCount < 2)
                {
                    // 我们把它清理干净,以避免保留任何旧工作的重要性。Count属性用于计划,因此不正确的值可能会破坏作业计划程序。
                    jobs = new QuickList<Job>();
                    return;
                }
                Debug.Assert(overlapHandlers.Length >= threadCount);
                const float jobMultiplier = 1.5f;
                var targetJobCount = Math.Max(1, jobMultiplier * threadCount);
                leafThreshold = (int)(tree.leafCount / targetJobCount);
                jobs = new QuickList<Job>((int)(targetJobCount * 2), Pool);
                NextNodePair = -1;
                this.OverlapHandlers = overlapHandlers;
                this.Tree = tree;
                // 收集工作。
                CollectJobsInNode(0, tree.leafCount, ref OverlapHandlers[0]);
            }

            /// <summary>
            /// 在多线程自检后清除。
            /// </summary>
            public void CompleteSelfTest()
            {
                // 请注意,包含0或1个条目的树不会有任何作业。
                if (jobs.Span.Allocated)
                    jobs.Dispose(Pool);
            }

            public unsafe void ExecuteJob(int jobIndex, int workerIndex)
            {
                ref var overlap = ref jobs[jobIndex];
                if (overlap.A >= 0)
                {
                    if (overlap.A == overlap.B)
                    {
                        // 相同的节点。
                        Tree.GetOverlapsInNode(ref Tree.Nodes[overlap.A], ref OverlapHandlers[workerIndex]);
                    }
                    else if (overlap.B >= 0)
                    {
                        // 不同的节点。
                        Tree.GetOverlapsBetweenDifferentNodes(ref Tree.Nodes[overlap.A], ref Tree.Nodes[overlap.B], ref OverlapHandlers[workerIndex]);
                    }
                    else
                    {
                        // A是内部节点,B是叶。
                        var leafIndex = Encode(overlap.B);
                        ref var leaf = ref Tree.Leaves[leafIndex];
                        ref var childOwningLeaf = ref Unsafe.Add(ref Tree.Nodes[leaf.NodeIndex].A, leaf.ChildIndex);
                        Tree.TestLeafAgainstNode(leafIndex, ref childOwningLeaf.Min, ref childOwningLeaf.Max, overlap.A, ref OverlapHandlers[workerIndex]);
                    }
                }
                else
                {
                    // A是一片叶子,B是内部的。
                    var leafIndex = Encode(overlap.A);
                    ref var leaf = ref Tree.Leaves[leafIndex];
                    ref var childOwningLeaf = ref Unsafe.Add(ref Tree.Nodes[leaf.NodeIndex].A, leaf.ChildIndex);
                    Tree.TestLeafAgainstNode(leafIndex, ref childOwningLeaf.Min, ref childOwningLeaf.Max, overlap.B, ref OverlapHandlers[workerIndex]);

                    // 请注意,我们不处理A和B都是叶子的情况。
                    // 收集例程应该会注意到这一点,因为它可以更方便地访问边界框,而且单个测试不值得原子增量。
                }
            }
            /// <summary>
            /// 执行多线程自检的单个辅助进程。
            /// </summary>
            /// <param name="workerIndex">执行这组测试的工作进程的索引。</param>
            public unsafe void PairTest(int workerIndex)
            {
                Debug.Assert(workerIndex >= 0 && workerIndex < OverlapHandlers.Length);
                int nextNodePairIndex;
                // 要最大限度地减少工作进程重叠列表的数量,请通过手动抓取下一个索引来执行直接负载平衡。
                while ((nextNodePairIndex = Interlocked.Increment(ref NextNodePair)) < jobs.Count)
                {
                    ExecuteJob(nextNodePairIndex, workerIndex);
                }
            }

            unsafe void DispatchTestForLeaf(int leafIndex, ref Vector3 leafMin, ref Vector3 leafMax, int nodeIndex, int nodeLeafCount, ref TOverlapHandler results)
            {
                if (nodeIndex < 0)
                {
                    results.Handle(leafIndex, Encode(nodeIndex));
                }
                else
                {
                    if (nodeLeafCount <= leafThreshold)
                        jobs.Add(new Job { A = Encode(leafIndex), B = nodeIndex }, Pool);
                    else
                        TestLeafAgainstNode(leafIndex, ref leafMin, ref leafMax, nodeIndex, ref results);
                }
            }

            unsafe void TestLeafAgainstNode(int leafIndex, ref Vector3 leafMin, ref Vector3 leafMax, int nodeIndex, ref TOverlapHandler results)
            {
                ref var node = ref Tree.Nodes[nodeIndex];
                ref var a = ref node.A;
                ref var b = ref node.B;
                // 尽管进行了递归,Leaf Bound应该保持在L1中-它将从这里一直沿递归使用。
                // 然而,虽然我们可能在加载子A时加载子B,但不能保证它会一直存在。
                // 与将派生数据保留在堆栈上相比,在驱逐情况下重新加载它需要更多的工作。
                // TODO：这是一些非常有问题的微调。发现叶子之后的递归长度足以驱逐L1的情况并不常见。一定要测试一下。
                var bIndex = b.Index;
                var bLeafCount = b.LeafCount;
                var aIntersects = BoundingBox.Intersects(leafMin, leafMax, a.Min, a.Max);
                var bIntersects = BoundingBox.Intersects(leafMin, leafMax, b.Min, b.Max);
                if (aIntersects)
                {
                    DispatchTestForLeaf(leafIndex, ref leafMin, ref leafMax, a.Index, a.LeafCount, ref results);
                }
                if (bIntersects)
                {
                    DispatchTestForLeaf(leafIndex, ref leafMin, ref leafMax, bIndex, bLeafCount, ref results);
                }
            }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            unsafe void DispatchTestForNodes(ref NodeChild a, ref NodeChild b, ref TOverlapHandler results)
            {
                if (a.Index >= 0)
                {
                    if (b.Index >= 0)
                    {
                        if (a.LeafCount + b.LeafCount <= leafThreshold)
                            jobs.Add(new Job { A = a.Index, B = b.Index }, Pool);
                        else
                            GetJobsBetweenDifferentNodes(ref Tree.Nodes[a.Index], ref Tree.Nodes[b.Index], ref results);

                    }
                    else
                    {
                        // 叶B对节点A。
                        TestLeafAgainstNode(Encode(b.Index), ref b.Min, ref b.Max, a.Index, ref results);
                    }
                }
                else if (b.Index >= 0)
                {
                    // 叶A对节点B。
                    TestLeafAgainstNode(Encode(a.Index), ref a.Min, ref a.Max, b.Index, ref results);
                }
                else
                {
                    // 两片叶子。
                    results.Handle(Encode(a.Index), Encode(b.Index));
                }
            }

            unsafe void GetJobsBetweenDifferentNodes(ref Node a, ref Node b, ref TOverlapHandler results)
            {
                // 没有共享的子项,因此请将其全部测试。

                ref var aa = ref a.A;
                ref var ab = ref a.B;
                ref var ba = ref b.A;
                ref var bb = ref b.B;
                var aaIntersects = Intersects(aa, ba);
                var abIntersects = Intersects(aa, bb);
                var baIntersects = Intersects(ab, ba);
                var bbIntersects = Intersects(ab, bb);

                if (aaIntersects)
                {
                    DispatchTestForNodes(ref aa, ref ba, ref results);
                }
                if (abIntersects)
                {
                    DispatchTestForNodes(ref aa, ref bb, ref results);
                }
                if (baIntersects)
                {
                    DispatchTestForNodes(ref ab, ref ba, ref results);
                }
                if (bbIntersects)
                {
                    DispatchTestForNodes(ref ab, ref bb, ref results);
                }

            }

            unsafe void CollectJobsInNode(int nodeIndex, int leafCount, ref TOverlapHandler results)
            {
                if (leafCount <= leafThreshold)
                {
                    jobs.Add(new Job { A = nodeIndex, B = nodeIndex }, Pool);
                    return;
                }

                ref var node = ref Tree.Nodes[nodeIndex];
                ref var a = ref node.A;
                ref var b = ref node.B;

                var ab = Intersects(a, b);

                if (a.Index >= 0)
                    CollectJobsInNode(a.Index, a.LeafCount, ref results);
                if (b.Index >= 0)
                    CollectJobsInNode(b.Index, b.LeafCount, ref results);

                if (ab)
                {
                    DispatchTestForNodes(ref a, ref b, ref results);
                }

            }
        }
    }
}
